from chapter6.ga_tsp import City, generate_city, GeneticAlgorithm
import time
def dp_algo(distances_array):
    n = len(distances_array) # 城市数量
    all_points_set = set(range(n)) # 为城市编号
    # cost-key：键值代表当前状态，它是一个队列，
    # 包含两个参数（已访问结点集合,最后一个访问结点）
    # cost-value：值代表了到达该状态的最优解，它是一个队列，
    # 有两个参数（路径距离，倒数第二个访问结点）
    cost = {}
    # queue里面的元素包含两个参数
    # （已经访问过的结点，最后一个访问结点），也就是cost的键值
    queue = [] # 开放队列保存将要访问的状态
    for i in range(n):
        # 初始状态就是只一个结点，距离为0，没有倒数第二个结点用None表示
        cost[(tuple([i]), i)] = tuple([0, None])
        queue.append((tuple([i]), i))
    while queue:
        prev_visited, prev_last_point = queue.pop(0) # 获取一个入口，开始搜索
        prev_dist, _ = cost[(prev_visited, prev_last_point)]
        # 排除已经访问的结点，剩下将要访问的结点
        to_visit = all_points_set.difference(set(prev_visited))
        for new_last_point in to_visit:
            # 遍历所有未访问结点
            new_visited = tuple(sorted(list(prev_visited) + [new_last_point]))
            # 添加新结点后，更新路径距离
            new_dist = prev_dist + distances_array[prev_last_point][new_last_point]
            if (new_visited, new_last_point) not in cost:
                # 如果没有在cost找到，添加新的元素
                cost[(new_visited, new_last_point)] = (new_dist, prev_last_point)
                # 把新状态添加进去
                queue += [(new_visited, new_last_point)]
            else:
                # 如果已经有存在cost表中，看是否获得更小的代价，若有则更新值
                if new_dist < cost[(new_visited, new_last_point)][0]:
                    cost[(new_visited, new_last_point)] = (new_dist, prev_last_point)
    # 通过cost表回溯最优路径和计算最短路程
    return retrace_optimal_path(cost, n)

def retrace_optimal_path(cost, n):
    points_to_retrace = tuple(range(n)) # 未访问城市数量，初始值为总城市数量
    path_key = None # 记录最短距离的状态键值
    optimal_cost = float('inf') # 记录最短路径值
    for k, v in cost.items():
        # 是否为遍历所有城市的状态的解
        if k[0] == points_to_retrace:
            if v[0] < optimal_cost:
                optimal_cost = v[0]
                path_key = k
    last_point = path_key[1] # 键值的第二个值是最后访问的城市
    next_to_last_point = cost[path_key][1] # 找到倒数第二个访问的结点
    optimal_path = [last_point] # 记录最优路径
    points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))
    while next_to_last_point is not None: # 还存在未访问城市，继续循环
        last_point = next_to_last_point
        path_key = (points_to_retrace, last_point) # 构建键值
        next_to_last_point = cost[path_key][1] # 找到上一个城市
        optimal_path = [last_point] + optimal_path # 添加到最优路径
        # 更新未访问城市
        points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))
    return optimal_path, optimal_cost

if __name__ == '__main__':
    input_size = 5
    citys, distances_array = generate_city(input_size)
    ga = GeneticAlgorithm(city_list=citys, population_size=50,
                          elite_size=5, mutation_rate=0.01, generations=80)
    t = time.time()
    result = ga.run()
    runtime = round(time.time() - t, 3)
    print('遗传算法运行时间', runtime)
    t = time.time()
    optimal_path, optimal_cost = dp_algo(distances_array)
    print(f"最短路径: {round(optimal_cost, 3)}")
    runtime = round(time.time() - t, 3)
    print('动态规划运行时间', runtime)